package com.demo.java.OD601_650.OD625;

import java.util.Scanner;
import java.util.Arrays;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【最大平分数组(A卷-100分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146884807
 */
public class OdMain {
    public static void main(String[] args) {
        // 处理输入
        Scanner in = new Scanner(System.in);
        String param_str = in.nextLine();
        int count = Integer.valueOf(param_str);

        // 构造输入数据结构,并求和
        int[] nums = new int[count];
        String num_str = in.nextLine();
        int sum = 0;
        String[] num_list = num_str.split(" ");
        for (int i = 0; i < count; i++) {
            nums[i] = Integer.valueOf(num_list[i]);
            sum += Integer.valueOf(num_list[i]);
        }

        // 最大可以等分为 m 个子数组
        for (int i = count; i > 0; i--) {
            // 从最大的可能行开始，满足条件即为为最小的情况
            if (canPartitionKSubsets(nums, i, sum)) {
                System.out.println(i);
                break;
            }
        }
    }

    // 判断能否将 nums 划分为 k 个和为 sum / k 的子集
    public static boolean canPartitionKSubsets(int[] nums, int k, int all) {
        // 如果总和不能整除 k，则直接返回 false
        if (all % k != 0) {
            return false;
        }

        // 每个子集的目标和
        int per = all / k;

        // 排序，优化后续处理（从大到小处理有助于剪枝）
        Arrays.sort(nums);
        int n = nums.length;

        // 如果数组中的最大值大于每个子集的目标和，直接返回 false
        if (nums[n - 1] > per) {
            return false;
        }

        // 状态压缩 DP 数组
        boolean[] dp = new boolean[1 << n];
        // curSum 数组记录每个状态下的当前子集和
        int[] curSum = new int[1 << n];
        dp[0] = true; // 初始化状态，表示没有选择任何元素时合法

        // 枚举所有可能的子集状态
        for (int i = 0; i < 1 << n; i++) {
            if (!dp[i]) {
                continue;
            }

            // 遍历所有未使用的元素
            for (int j = 0; j < n; j++) {
                // 如果该元素已经被选择过，跳过
                if (((i >> j) & 1) != 0) {
                    continue;
                }

                // 计算当前状态下加上 nums[j] 后的新的子集和
                int next = i | (1 << j);
                if (curSum[i] + nums[j] > per) {
                    break; // 当前和已经超过目标值，剪枝
                }

                // 更新状态和对应的子集和
                if (!dp[next]) {
                    curSum[next] = (curSum[i] + nums[j]) % per;
                    dp[next] = true;
                }
            }
        }

        // 最终状态，表示所有元素都被使用且成功划分
        return dp[(1 << n) - 1];
    }
}